#include<iostream>
#include<vector>
#include<queue>
#include<string>
using namespace std;




struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
class Solution {
public:
    // TreeNode* Left(TreeNode*t)
    // {
    //  while(t->left)
    //  {
    //      t=t->left;
    //  }
    //  return t;
    // }
    void INOrder(TreeNode* cur, TreeNode*& prev) {
        if (cur == nullptr) {
            return;
        }

        INOrder(cur->left, prev);
        cur->left = prev;
        if (prev) {
            prev->right = cur;
        }
        prev = cur;
        INOrder(cur->right, prev);

    }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        //TreeNode*head=Left(pRootOfTree);
        if (pRootOfTree == nullptr) {
            return nullptr;
        }
        TreeNode* prev = nullptr;
        INOrder(pRootOfTree, prev);


        TreeNode* head = pRootOfTree;
        while (head->left)
        {
            head = head->left;
        }

        while (prev != head)
        {
            prev = prev->left;
        }

        // prev->right=head;
        // head->left=prev;



        return prev;
    }
};
